package leetcode;

public class Code003_RobotWalk {

    /**
     * 暴力递归方法
     *
     * @param N    机器人活动范围 1-N
     * @param end  最终目标
     * @param cur  当前位置
     * @param rest 剩余步数
     * @return
     */
    public static int f(int N, int end, int cur, int rest) {
        if (rest == 0) {
            return cur == end ? 1 : 0;
        }
        // rest > 0，有路可走
        if (cur == 1) {
            return f(N, end, cur + 1, rest - 1);
        }
        if (cur == N) {
            return f(N, end, cur - 1, rest - 1);
        }
        return f(N, end, cur + 1, rest - 1) + f(N, end, cur - 1, rest - 1);
    }


    // 记忆搜索
    public static int robotWalk2(int N, int end, int S, int K) {
        int[][] dp = new int[S + 1][K + 1];
        for (int i = 0; i <= S; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        return f2(N, end, S, K, dp);
    }

    public static int f2(int N, int end, int cur, int rest, int[][] dp) {
        //缓存命中直接返回缓存值
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        // 缓存未命中
        if (rest == 0) {
            dp[cur][rest] = cur == end ? 1 : 0;
            return dp[cur][rest];
        }
        // rest > 0，有路可走
        if (cur == 1) {
            dp[cur][rest] = f(N, end, cur + 1, rest - 1);
        } else if (cur == N) {
            dp[cur][rest] = f(N, end, cur - 1, rest - 1);
        } else {
            dp[cur][rest] = f(N, end, cur + 1, rest - 1) + f(N, end, cur - 1, rest - 1);
        }
        return dp[cur][rest];
    }


    public static void main(String[] args) {
        //int a = f(20, 4, 2, 20);
        int a = robotWalk2(5, 4, 2, 4);
        System.out.println(a);
    }
}
